package fcrypt

//求两个数最大公因数
func Gcd(a, b int) int {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

//求a关于m的模逆
func GetModInverse(a, m int) int {
	if Gcd(a, m) != 1 {
		return 0
	}
	x1, x2, x3 := 1, 0, a
	y1, y2, y3 := 0, 1, m
	q := 0
	t1, t2, t3 := 0, 0, 0
	for y3 != 0 {
		q = x3 / y3
		t1 = x1 - q*y1
		t2 = x2 - q*y2
		t3 = x3 - q*y3
		x1 = y1
		x2 = y2
		x3 = y3
		y1 = t1
		y2 = t2
		y3 = t3
	}
	return (x1 + m) % m
}
